package com.ls.eightSort;

/**
 * 归并排序代码
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {9,6,5,4,2,5};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        show(arr);
    }

    /**
     * 分
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        int mid = (left + right)>>1;
        if (left < right){
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,right,temp);
        }
    }


    /**
     * 治
     */
    public static void merge(int[] arr, int left, int right, int[] temp){
        int i = left;
        int mid = (left + right)>>1;
        int j = mid+1;
        int t = 0;
        // 1.按照规则进行合并,放进临时数组中
        while (i<=mid && j<= right){
            if (arr[i]<=arr[j]){
                temp[t] = arr[  i];
                ++t;
                ++i;
            }else {
                temp[t] = arr[j];
                ++t;
                ++j;
            }
        }
        //2.将剩余拼接
        while (i<=mid){
            // 左边剩余
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j<=right){
            // 右边剩余
            temp[t] = arr[j];
            t++;
            j++;
        }

        // 3.将有序的temp部分拷贝回arr
        t = 0;
        while (left<=right){
            arr[left] = temp[t];
            ++left;
            ++t;
        }
    }

    public static void show(int[] arr){
        for (int i : arr) {
            System.out.print(i+",");
        }
        System.out.println();

    }




}
